home *** CD-ROM | disk | FTP | other *** search
/ Gekikoh Dennoh Club 5 / Gekikoh Dennoh Club Vol. 5 (Japan).7z / Gekikoh Dennoh Club Vol. 5 (Japan) (Track 01).bin / internet / xip / iijppp.lzh / src / pred.c < prev    next >
C/C++ Source or Header  |  1994-09-30  |  5KB  |  216 lines
  1. #include "fsm.h"
  2. #include "hdlc.h"
  3. #include "lcpproto.h"
  4. #include "ccp.h"
  5.  
  6. /*
  7.  * pred.c -- Test program for Dave Rand's rendition of the
  8.  * predictor algorithm
  9.  * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson)
  10.  * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de>
  11.  * Original  : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
  12.  */
  13.  
  14. /* The following hash code is the heart of the algorithm:
  15.  * It builds a sliding hash sum of the previous 3-and-a-bit characters
  16.  * which will be used to index the guess table.
  17.  * A better hash function would result in additional compression,
  18.  * at the expense of time.
  19.  */
  20. #define IHASH(x) iHash = (iHash << 4) ^ (x)
  21. #define OHASH(x) oHash = (oHash << 4) ^ (x)
  22.  
  23. static unsigned short int iHash, oHash;
  24. static unsigned char InputGuessTable[65536];
  25. static unsigned char OutputGuessTable[65536];
  26.  
  27. static int
  28. compress(source, dest, len)
  29. unsigned char *source, *dest;
  30. int len;
  31. {
  32.     int i, bitmask;
  33.     unsigned char *flagdest, flags, *orgdest;
  34.  
  35.     orgdest = dest;
  36.     while (len) {
  37.         flagdest = dest++; flags = 0;   /* All guess wrong initially */
  38.         for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
  39.             if (OutputGuessTable[oHash] == *source) {
  40.                 flags |= bitmask;       /* Guess was right - don't output */
  41.             } else {
  42.                 OutputGuessTable[oHash] = *source;
  43.                 *dest++ = *source;      /* Guess wrong, output char */
  44.             }
  45.             OHASH(*source++);len--;
  46.         }
  47.         *flagdest = flags;
  48.     }
  49.     return(dest - orgdest);
  50. }
  51.  
  52. static void
  53. SyncTable(source, dest, len)
  54. unsigned char *source, *dest;
  55. int len;
  56. {
  57.     int i;
  58.  
  59.     while (len--) {
  60.         if (InputGuessTable[iHash] != *source) {
  61.             InputGuessTable[iHash] = *source;
  62.         }
  63.         IHASH(*dest++ = *source++);
  64.     }
  65. }
  66.  
  67. static int
  68. decompress(source, dest, len)
  69. unsigned char *source, *dest;
  70. int len;
  71. {
  72.     int i, bitmask;
  73.     unsigned char flags, *orgdest;
  74.  
  75.     orgdest = dest;
  76.     while (len) {
  77.         flags = *source++;
  78.         len--;
  79.         for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
  80.             if (flags & bitmask) {
  81.                 *dest = InputGuessTable[iHash];       /* Guess correct */
  82.             } else {
  83.                 if (!len)
  84.                     break;      /* we seem to be really done -- cabo */
  85.                 InputGuessTable[iHash] = *source;     /* Guess wrong */
  86.                 *dest = *source++;              /* Read from source */
  87.                 len--;
  88.             }
  89.             IHASH(*dest++);
  90.         }
  91.     }
  92.     return(dest - orgdest);
  93. }
  94.  
  95. #define SIZ1 2048
  96.  
  97. void
  98. Pred1Init(direction)
  99. int direction;
  100. {
  101.   if (direction & 1) {    /* Input part */
  102.     iHash = 0;
  103.     bzero(InputGuessTable, sizeof(InputGuessTable));
  104.   }
  105.   if (direction & 2) { /* Output part */
  106.     oHash = 0;
  107.     bzero(OutputGuessTable, sizeof(OutputGuessTable));
  108.   }
  109. }
  110.  
  111. void
  112. Pred1Output(pri, proto, bp)
  113. int pri;
  114. u_short proto;
  115. struct mbuf *bp;
  116. {
  117.   struct mbuf *mwp;
  118.   u_char *cp, *wp, *hp;
  119.   int orglen, len;
  120.   u_char bufp[SIZ1];
  121.   u_short fcs;
  122.  
  123.   orglen = plength(bp) + 2;    /* add count of proto */
  124.   mwp = mballoc((orglen+2)/8*9+12, MB_HDLCOUT);
  125.   hp = wp = MBUF_CTOP(mwp);
  126.   cp = bufp;
  127.   *wp++ = *cp++ = orglen >> 8;
  128.   *wp++ = *cp++ = orglen & 0377;
  129.   *cp++ = proto >> 8;
  130.   *cp++ = proto & 0377;
  131.   mbread(bp, cp, orglen-2);
  132.   fcs = HdlcFcs(INITFCS, bufp, 2+orglen);
  133.   fcs = ~fcs;
  134.  
  135.   len = compress(bufp + 2, wp, orglen);
  136. #ifdef DEBUG
  137.   logprintf("orglen (%d) --> len (%d)\n", orglen, len);
  138. #endif
  139.   CcpInfo.orgout += orglen;
  140.   if (len < orglen) {
  141.     *hp |= 0x80;
  142.     wp += len;
  143.     CcpInfo.compout += len;
  144.   } else {
  145.     bcopy(bufp+2, wp, orglen);
  146.     wp += orglen;
  147.     CcpInfo.compout += orglen;
  148.   }
  149.  
  150.   *wp++ = fcs & 0377;
  151.   *wp++ = fcs >> 8;
  152.   mwp->cnt = wp - MBUF_CTOP(mwp);
  153.   HdlcOutput(pri, PROTO_COMPD, mwp);
  154. }
  155.  
  156. void
  157. Pred1Input(bp)
  158. struct mbuf *bp;
  159. {
  160.   u_char *cp, *pp;
  161.   int len, olen, len1;
  162.   struct mbuf *wp;
  163.   u_char *bufp;
  164.   u_short fcs, proto;
  165.  
  166.   wp = mballoc(SIZ1, MB_IPIN);
  167.   cp = MBUF_CTOP(bp);
  168.   olen = plength(bp);
  169.   pp = bufp = MBUF_CTOP(wp);
  170.   *pp++ = *cp & 0177;
  171.   len = *cp++ << 8;
  172.   *pp++ = *cp;
  173.   len += *cp++;
  174.   CcpInfo.orgin += len & 0x7fff;
  175.   if (len & 0x8000) {
  176.     len1 = decompress(cp, pp, olen - 4);
  177.     CcpInfo.compin += olen;
  178.     len &= 0x7fff;
  179.     if (len != len1) {    /* Error is detected. Send reset request */
  180.       CcpSendResetReq(&CcpFsm);
  181.       pfree(bp);
  182.       return;
  183.     }
  184.     cp += olen - 4;
  185.     pp += len1;
  186.   } else {
  187.     CcpInfo.compin += len;
  188.     SyncTable(cp, pp, len);
  189.     cp += len;
  190.     pp += len;
  191.   }
  192.   *pp++ = *cp++;    /* CRC */
  193.   *pp++ = *cp++;
  194.   fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp);
  195. #ifdef DEBUG
  196.   logprintf("fcs = %04x (%s), len = %x, olen = %x\n",
  197.        fcs, (fcs == GOODFCS)? "good" : "bad", len, olen);
  198. #endif
  199.   if (fcs == GOODFCS) {
  200.     wp->offset += 2;        /* skip length */
  201.     wp->cnt -= 4;        /* skip length & CRC */
  202.     pp = MBUF_CTOP(wp);
  203.     proto = *pp++;
  204.     if (proto & 1) {
  205.       wp->offset++;
  206.       wp->cnt--;
  207.     } else {
  208.       wp->offset += 2;
  209.       wp->cnt -= 2;
  210.       proto = (proto << 8) || *pp++;
  211.     }
  212.     DecodePacket(proto, wp);
  213.   }
  214.   pfree(bp);
  215. }
  216.